Collaborative applications are relevant programs allowing many users to simultaneously cooperate in order to perform a given task on a shared object. These applications are based on replicating shared objects in order to ensure data availability. The Operational Transformation (OT) approach is used for supporting optimistic replication in these applications. It allows the users to concurrently update the shared data and exchange their updates in any order since the convergence of all replicas, i.e. the fact that all users view the same data, is ensured in all cases. Undoing operations is an indispensable feature for many collaborative applications mainly collaborative editors. It provides the ability to restore a correct state of the shared data after erroneous operations. In particulary, selective undo allows user to undo any operation and is based on rearranging operations in the history. Combining OT and undo approaches is a challenging problem. Even though various undo solutions have been proposed over the recent years, verifying their correctness still be a challenging problem due to the absence of formal guidelines for undo. In this report, we address the undo problem from a theoretical point of view. As the main contribution, we propose a necessary and sufficient condition for undoing replicated objects based on OT with respect to three inverse properties. To overcome the difficulty of necessity proof, we use Constraint Satisfaction Problems (CSP) theory in order to cover all possible transformation cases. As the main result, we prove that it is impossible to achieve a correct undo for objects with non- commutative operations. To relax this impossibility result, we sketch a preliminary solution that consists in adding explicitly a new form of idle operations.

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001F83 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001F83 | SxmlIndent | more

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     Hal:hal-00646127
   |texte=   On the Undoability Problem in Distributed Collaborative Applications
}}